package com.myown.structure.impl;

import com.myown.structure.TreeNode;

/**
 * 自平衡二叉查找树 (<TT>AVL</TT>) <p>
 *
 * @author lincky
 * @version v1.0.0
 * @time 2017.02.25 13:56
 */
public class BinaryTree<E extends Comparable<E>> extends AbstactTree<E> {

    /**
     * 左高
     */
    private static final int WEIGHT_LEFT = 1;

    /**
     * 等高
     */
    private static final int WEIGHT_BALANCE = 0;

    /**
     * 右高
     */
    private static final int WEIGHT_RIGHT = -1;

    public BinaryTree() {
    }

    /**
     * 平衡而二叉树的插入操作 <p>
     *
     * 树结构调整原理：{@link #singleInsert(TreeNode, TreeNode)} <p>
     *
     * 平衡因子调整原理：{@link #balanceAfterInsertion(Node)}<p>
     *
     * @param node 插入节点的父节点
     * @param item 节点元素
     */
    @Override
    public void insert(TreeNode<E> node, E item) {
        TreeNode<E> newNode = new Node<E>(item);
        singleInsert(node, newNode);
        balanceAfterInsertion((Node<E>) newNode);
    }

    /**
     * 平衡二叉树的删除操作 <p>
     *
     * 树结构调整原理:{@link #singleDelete(TreeNode)} <p>
     *
     * 平衡因子调整原理:{@link #balanceAfterDeletion(Node)} <p>
     *
     * @param node 待删除节点
     */
    @Override
    public void delete(TreeNode<E> node) {
        balanceAfterDeletion((Node<E>) singleDelete(node));
    }

    /**
     * 调整的方法： <p>
     * 1.当最小不平衡子树的根(以下简称R)为2时，即左子树高于右子树：
     * 如果R的左子树的根节点的BF为1时，做右旋；
     * 如果R的左子树的根节点的BF为-1时，先左旋然后再右旋 <p>
     *
     * 2.R为-2时，即右子树高于左子树：
     * 如果R的右子树的根节点的BF为1时，先右旋后左旋
     * 如果R的右子树的根节点的BF为-1时，做左旋 <p>
     *
     * @param node 插入节点
     */
    private void balanceAfterInsertion(Node<E> node) {
        E item = node.item;
        // 自下向上回溯，查找最近不平衡节点(-2, 2)
        while ((node = (Node<E>) node.parent) != null) {
            // 左树右树
            if (node.item().compareTo(item) > 0) {
                node.balance++;
            } else {
                node.balance--;
            }
            if (node.balance == 0) {
                break;
            }
            if (!node.balance()) {
                if (node.balance == 2) {
                    leftBalance(node);
                }
                if (node.balance == -2) {
                    rightBalance(node);
                }
                break;
            }
        }
    }

    /**
     * 删除某节点node后的调整方法： <p>
     * 1.从node开始向上回溯，修改祖先的BF值，这里只要调整从p的父节点到根节点的BF值，
     * 调整原则为，当p位于某祖先节点(简称A)的左子树中时，A的BF减1，当p位于A的
     * 右子树中时A的BF加1。当某个祖先节点BF变为1或-1时停止回溯，这里与插入是相反的，
     * 因为原本这个节点是平衡的，删除它的子树的某个节点并不会改变它的高度 <p>
     *
     * 2.检查每个节点的BF值，如果为2或-2需要进行旋转调整，调整方法如下文，
     * 如果调整之后这个最小子树的高度降低了，那么必须继续从这个最小子树的根节点(假设为B)继续
     * 向上回溯，这里和插入不一样，因为B的父节点的平衡性因为其子树B的高度的改变而发生了改变，
     * 那么就可能需要调整，所以删除可能进行多次的调整。 <p>
     *
     * @param node 最小平衡节点
     */
    private void balanceAfterDeletion(Node<E> node) {
        if (node == null) {
            return;
        }
        boolean heightLower = true;
        Node<E> parent = (Node<E>) node.parent;
        // 自下向上回溯，查找最近不平衡节点(-2, 2)
        while (parent != null && heightLower) {
            // 左树右树
            if (node.item.compareTo(parent.item) < 0) {
                parent.balance--;
            } else {
                parent.balance++;
            }
            // 若平衡因子为|1|，即调整前为0，则停止调整
            if (Math.abs(parent.balance) == 1) {
                break;
            }
            if (parent.balance == 2) {
                heightLower = leftBalance(parent);
            } else if (parent.balance == -2) {
                heightLower = rightBalance(parent);
            }
            parent = (Node<E>) parent.parent;
        }
    }

    /**
     * 左平衡处理 <p>
     *
     * @param node 节点
     * @return <tt>true</tt> - 平衡
     */
    private boolean leftBalance(Node<E> node) {
        assert !node.balance();
        /*
         * 平衡因子的调整如图：
         *         t                       rd
         *       /   \                   /    \
         *      l    tr   左旋后右旋    l       t
         *    /   \       ------->    /  \    /  \
         *  ll    rd                ll   rdl rdr  tr
         *       /   \
         *     rdl  rdr
         *
         *   情况2(rd的BF为0)
         *
         *
         *         t                       rd
         *       /   \                   /    \
         *      l    tr   左旋后右旋    l       t
         *    /   \       ------->    /  \       \
         *  ll    rd                ll   rdl     tr
         *       /
         *     rdl
         *
         *   情况1(rd的BF为1)
         *
         *
         *         t                       rd
         *       /   \                   /    \
         *      l    tr   左旋后右旋    l       t
         *    /   \       ------->    /       /  \
         *  ll    rd                ll       rdr  tr
         *           \
         *          rdr
         *
         *   情况3(rd的BF为-1)
         *
         *
         *         t                         l
         *       /       右旋处理          /    \
         *      l        ------>          ll     t
         *    /   \                             /
         *   ll   rd                           rd
         *   情况4(L等高)
         */
        boolean heightLower = true;
        Node<E> left = (Node<E>) node.left;
        switch (left.balance) {
            // LL型 右旋
            case WEIGHT_LEFT:
                node.balance = left.balance = WEIGHT_BALANCE;
                rightRotate(node);
                break;
            // LR型 左旋右旋
            case WEIGHT_RIGHT:
                Node<E> leftRight = (Node<E>) left.right;
                switch (leftRight.balance) {
                    // 情况1
                    case WEIGHT_LEFT:
                        node.balance = WEIGHT_RIGHT;
                        left.balance = WEIGHT_BALANCE;
                        break;
                    // 情况2
                    case WEIGHT_BALANCE:
                        node.balance = left.balance = WEIGHT_BALANCE;
                        break;
                    // 情况3
                    case WEIGHT_RIGHT:
                        node.balance = WEIGHT_BALANCE;
                        left.balance = WEIGHT_LEFT;
                        break;
                }
                leftRight.balance = WEIGHT_BALANCE;
                leftRotate(left);
                rightRotate(node);
                break;
            // 情况4
            case WEIGHT_BALANCE:
                left.balance = WEIGHT_RIGHT;
                node.balance = WEIGHT_LEFT;
                rightRotate(node);
                heightLower = false;
                break;
        }
        return heightLower;
    }

    private boolean rightBalance(Node<E> node) {
        assert !node.balance();
        /*
         * 做右平衡处理
         * 平衡因子的调整如图：
         *           t                               ld
         *        /     \                          /     \
         *      tl       r       先右旋再左旋     t       r
         *             /   \     -------->      /   \    /  \
         *           ld    rr                 tl   ldl  ldr rr
         *          /  \
         *       ldl  ldr
         *       情况2(ld的BF为0)
         *
         *           t                               ld
         *        /     \                          /     \
         *      tl       r       先右旋再左旋     t       r
         *             /   \     -------->      /   \       \
         *           ld    rr                 tl   ldl      rr
         *          /
         *       ldl
         *       情况1(ld的BF为1)
         *
         *           t                               ld
         *        /     \                          /     \
         *      tl       r       先右旋再左旋     t       r
         *             /   \     -------->      /        /  \
         *           ld    rr                 tl        ldr rr
         *             \
         *             ldr
         *       情况3(ld的BF为-1)
         *
         *           t                                  r
         *             \          左旋                /   \
         *              r        ------->           t      rr
         *            /   \                          \
         *           ld   rr                         ld
         *        情况4(r的BF为0)
         */
        boolean heightLower = true;
        Node<E> right = (Node<E>) node.right;
        switch (right.balance) {
            // RR型 左旋
            case WEIGHT_RIGHT:
                node.balance = right.balance = WEIGHT_BALANCE;
                leftRotate(node);
                break;
            // RL型 右旋左旋
            case WEIGHT_LEFT:
                Node<E> rightLeft = (Node<E>) right.left;
                switch (rightLeft.balance) {
                    // 情况1
                    case WEIGHT_LEFT:
                        node.balance = WEIGHT_BALANCE;
                        right.balance = WEIGHT_RIGHT;
                        break;
                    // 情况2
                    case WEIGHT_BALANCE:
                        node.balance = right.balance = WEIGHT_BALANCE;
                        break;
                    // 情况3
                    case WEIGHT_RIGHT:
                        node.balance = WEIGHT_LEFT;
                        right.balance = WEIGHT_BALANCE;
                        break;
                }
                rightLeft.balance = WEIGHT_BALANCE;
                rightRotate(right);
                leftRotate(node);
                break;
            // 情况4
            case WEIGHT_BALANCE:
                right.balance = WEIGHT_LEFT;
                node.balance = WEIGHT_RIGHT;
                leftRotate(node);
                heightLower = false;
                break;
        }
        return heightLower;
    }

    @Override
    void valid(TreeNode<E> node) {
        Node<E> nodeExp = (Node<E>) node;
        assert nodeExp.balance != 2 && nodeExp.balance != -2;
        if (nodeExp.left != null) {
            assert nodeExp.left.item().compareTo(nodeExp.item()) < 0;
            valid(nodeExp.left);
        }
        if (nodeExp.right != null) {
            assert nodeExp.right.item().compareTo(nodeExp.item()) > 0;
            valid(nodeExp.right);
        }
    }

    /**
     * 平衡二叉树树内部链接节点 <p>
     *
     * 节点结构：平衡因子，左孩子，右孩子，父亲节点，元素 <p>
     *
     * 节点性质：平衡因子 {@link #balance}
     *
     * @param <E> 存储数据类型
     */
    static class Node<E extends Comparable<E>> extends AbstactTree.Node<E> {
        /**
         * 设置平衡因子，平衡因子只有五种取值： <p>
         *
         * 平衡：<p>
         * {@link #WEIGHT_LEFT}：左高 <p>
         * {@link #WEIGHT_BALANCE}：平衡 <p>
         * {@link #WEIGHT_RIGHT}：右高 <p>
         *
         * 不平衡： <p>
         * 2： 左子树不平衡 <p>
         * -2： 右子树不平衡 <p>
         *
         */
        int balance;

        Node(E item) {
            super(item);
        }

        /**
         * 节点是否平衡 <p>
         *
         * @return <tt>true</tt> - 平衡
         */
        boolean balance() {
            return Math.abs(balance) != 2;
        }

    }

}
